#include<stdio.h>
#include<stdlib.h>
struct node
{
int val;
struct node *next;
};


void count2(struct node **tempt7)
{
	int a,count1=0;
	struct node *temp;
	temp=(*tempt7);
	printf("\nEnter the value to count the occurences of:");
	scanf("%d",&a);
	while(temp!=NULL)
	{
		if(temp->val==a)
		{
			count1++;
		}
		temp=temp->next;
	}
	if(count1==0)
	{
		printf("\nValue not found in List\n");
	}
	else
	{
		printf("\n\n%d is present %d times.\n\n",a,count1);
	}
}

void index1(struct node **tempt6)
{
	int i=-1,a,flag=0,flag1=0;
	struct node *temp;
	temp=(*tempt6);
	printf("Enter the value whose index is to be found out:");
	scanf("%d",&a);
	while(flag==0)
	{
		if (temp->val==a)
		{
			flag1=1;
			flag=1;
		}
		else
		if(temp==NULL)
		{
			flag1=0;
			flag=1;
		}
		else
		if(temp->next==NULL)
		{
			flag1=0;
			flag=1;
		}
		temp=temp->next;
		i++;
	}
	if(flag1==1)
	{
		printf("\nThe given value was found at %d positio\n\n",i);
	}
	else
	{
		printf("\nValue not Found\n\n");
	}
}

void append(struct node **tempt5)
{
	char a[1000];
	int b=0;
	struct node *temp;
	struct node *temp1;
	printf("Enter value to be appended:");
	scanf(" %s",a);
	b=atoi(a);
	temp=(*tempt5);
	temp1=malloc(sizeof(struct node));
	temp1->val=b;
	temp1->next=NULL;
	if(*tempt5==NULL)
	{
		(*tempt5)=temp1;
	}
	else
	{
		while(temp->next!=NULL)
		{
			temp=temp->next;
		}
		temp->next=temp1;
	}
	printf("\n\nValue appended to list\n");
}

void extend(struct node **tempt4)
{
	char a[1000]; //maximum length of a number is 1000 digits
	struct node *tempt=NULL;
	struct node *temp;
	struct node *temp1;
	int flag=0,b;
	printf("\nEnter the values one by one(pressing enter each time after a number\n\nINPUT CHARACTER 's' IN LOWER CASE TO STOP INPUT)\n");
	scanf(" %s",a);
	flag=strcmp(a,"s");
	while(flag!=0)
	{
		b=atoi(a);
		if(tempt==NULL)
		{
			tempt=malloc(sizeof(struct node));
			tempt->val=b;
			tempt->next=NULL;
		}
		else
		{
			temp=tempt;
			while(temp->next!=NULL)
			{
				temp=temp->next;
			}
			temp1=malloc(sizeof(struct node));
			temp->next=temp1;
			temp1->val=b;
			temp1->next=NULL;
		}
		scanf(" %s",a);
		flag=strcmp(a,"s");
	}
	temp=(*tempt4);
	if((*tempt4)==NULL)
	{
		(*tempt4)=tempt;
	}
	else
	{
		while(temp->next!=NULL)
		{
			temp=temp=temp->next;
		}
		temp->next=tempt;
		printf("\n\n List Extended\n");
	}
}

void insert(struct node **tempt)
{
	int size=1,pos=0,i=0;
	struct node *newn;
	struct node *temp;
	newn=malloc(sizeof(struct node));
	if((*tempt)==NULL)
	{
		temp=malloc(sizeof(struct node));
		temp->next=NULL;
		printf("Size of list is 0\n");
		printf("Enter the value:");
		fflush(stdin);
		scanf("%d",&(temp->val));
		(*tempt)=temp;
	}
	else
	{
		temp=(*tempt);
		while(temp->next!=NULL)
		{
			size++;
			temp=temp->next;
		}
		temp=(*tempt);
		printf("The current size of the list is %d\nEnter index value where value is to entered(0-%d)",size,size);
		scanf("%d",&pos);
		if(pos==0)
		{
			newn->next=temp;
			printf("Enter the value:");
			scanf("%d",&(newn->val));
			(*tempt)=newn;
		}
		else
		{
			while(i<(pos-1))
			{
				temp=temp->next;
				i++;
			}
			newn->next=temp->next;
			temp->next=newn;
			printf("Enter the value:");
			scanf("%d",&(newn->val));
		}
	}
}




void pop(struct node **tempt1)
{
	struct node *temp;
	struct node *deln;
	int pos=0,i=0;
	int size=1;
	if((*tempt1)==NULL)
	{
		printf("Underflow\n");
	}
	else
	{
		temp=(*tempt1);
		while(temp->next!=NULL)
		{
			size++;
			temp=temp->next;
		}
		printf("The current size of the list is %d\n",size);
		printf("Enter index value of the element to be deleted:(0-%d):",(size-1));
		scanf("%d",&pos);
		temp=(*tempt1);
		if (pos==0)
		{
			(*tempt1)=((*tempt1)->next);
			free(temp);
		}
		else
		if((size-1)==pos)
		{
			while(i<(pos-1))
			{
				i++;
				temp=temp->next;
			}
			deln=temp->next;
			temp->next=NULL;
			free(deln);
		}
		else
		{
			i=0;
			temp=(*tempt1);
			while(i<(pos-1))
			{
				i++;
				temp=temp->next;
			}
			deln=temp->next;
			temp->next=deln->next;
			free(deln);
		}
		printf("Element Popped\n\n");
	}
}

void reverse(struct node **tempt2)
{
	struct node *temp;
	struct node *temp1;
	struct node *temp3;
	temp=(*tempt2);
	temp1=temp->next;
	if(temp==NULL)
	{
		printf("List Empty\n\n");
	}
	else if(temp->next==NULL)
	{
		printf("Reversal Done\n\n");
	}
	else if(temp1->next==NULL)
	{
		temp1->next=temp;
		temp->next=NULL;
		(*tempt2)=temp1;
		printf("Reversal Done\n\n");
	}
	else
	{
		while(temp1!=NULL)
		{
			if(temp==(*tempt2))
			{
				temp->next=NULL;
				temp3=temp;
				temp=temp1;
				temp1=temp1->next;
			}
			else
			{
				temp->next=temp3;
				temp3=temp;
				temp=temp1;
				temp1=temp1->next;
			}
		}
		temp->next=temp3;
		(*tempt2)=temp;
	}

}

void remove1(struct node **tempt8)
{
	int num,flag=0;
	struct node *temp;
	struct node *temp1;
	temp=(*tempt8);
	temp1=temp->next;
	printf("\nEnter the value to be removed:");
	scanf("%d",&num);
	if((*tempt8)->val==num)
	{
		(*tempt8)=temp->next;
		free(temp);
		printf("\nValue removed\n");
	}
	else
	{
		while(temp1!=NULL)
		{
			if(temp1->val==num)
			{
				flag=1;
				break;
			}
			temp=temp->next;
			temp1=temp1->next;
		}
		if(flag==1)
		{
			temp->next=temp1->next;
			free(temp1);
			printf("\nValue removed\n");
		}
		else
		{
			printf("Value not present in list\n");
		}
	}

}

void print(struct node *temp3)
{
	struct node *temp;
	temp=temp3;
	if(temp==NULL)
	{
	printf("list empty\n");
	}
	else
	{
		printf("\n\n[");
		while(temp->next!=NULL)
		{
			printf("%d,",(temp->val));
			temp=temp->next;
		}
		printf("%d]\n\n",temp->val);
	}
}

void sort(struct node **tempt3)
{
	int flag=0,a;
	struct node *temp;
	struct node *temp1;
	struct node *temp2;
	struct node *temp3;
	struct node *temp4;
	temp=(*tempt3);
	while(temp->next!=NULL)
	{
		temp1=temp->next;
		temp2=temp1;
		if((temp->val)>(temp1->val))
		{
			if(temp==(*tempt3))
			{
				temp->next=temp1->next;
				temp1->next=temp;
				(*tempt3)=temp1;
			}
			else
			{
				temp3=(*tempt3);
				temp4=temp3->next;
				if((temp1->val)<(temp3->val))
				{
					temp->next=temp1->next;
					temp1->next=temp3;
					(*tempt3)=temp1;
				}
				else
				{
					flag=0;
					while((temp4!=temp) && (temp4->val<temp1->val))
					{

						if(temp4->val>temp1->val)
						{
							break;
						}
						if(temp4->next==temp && temp4->val<temp1->val)
						{
							flag=1;
							break;
						}
						temp3=temp3->next;
						temp4=temp4->next;
					}
					if (flag==0)
					{
						temp->next=temp1->next;
						temp3->next=temp1;
						temp1->next=temp4;
					}
				}
			}
		}
		temp=temp2;
	}
	temp=(*tempt3);
	temp1=temp->next;
	temp2=temp1->next;
	while(temp2->next!=NULL)
	{
		temp=temp->next;
		temp1=temp1->next;
		temp2=temp2->next;
	}
	if((temp1->val)>(temp2->val))
	{
		temp->next=temp2;
		temp2->next=temp1;
		temp1->next=NULL;
	}
	printf("\n    Sort in:\n");
	printf("   1.Ascending Order\n");
	printf("   2.Descending Order\n");
	printf("Enter choice:");
	scanf("%d",&a);
	switch(a)
	{
		case 1:{printf("\n\nList sorted\n\n");break;}
		case 2:{reverse(tempt3);printf("\n\nList Sorted\n\n");break;}
		default:{printf("\n\nWrong Choice\n");break;}
	};
}


int main()
{
	struct node *top=NULL;
	struct node *rear=NULL;
	int a;
	char b='y';
	while ((b=='Y') || (b=='y'))
	{
		printf("\n\n            Main Menu               \n");
		printf("            1.Extend with a List        \n");
		printf("            2.Append one element        \n");
		printf("            3.Insert an element         \n");
		printf("            4.Pop an element            \n");
		printf("            5.Remove an element         \n");
		printf("            6.Find Index of element     \n");
		printf("            7.Count number of occurences\n");
		printf("            8.reverse the List          \n");
		printf("            9.Sort                      \n");
		printf("            10.Print                     \n");
		printf("            11.Exit                      \n");
		printf("            Enter Your Choice:");
		fflush(stdin);
		scanf("%d",&a);
		switch(a)
		{
			case 1:{extend(&top);break;}
			case 2:{append(&top);break;}
			case 3:{insert(&top);break;}
			case 4:{pop(&top);break;}
			case 5:{remove1(&top);break;}
			case 6:{index1(&top);break;}
			case 7:{count2(&top);break;}
			case 8:{reverse(&top);printf("Reversal Done\n");break;}
			case 9:{sort(&top);break;}
			case 10:{print(top);break;}
			case 11:{return 0;break;}
			default:{printf("wrong choice\n");break;}
		};
		printf("Do you want to continue?");
		fflush(stdin);
		scanf("%c",&b);
	}
	return 0;
}